1. Field of the Invention
The present invention relates generally to coordination amongst execution sequences in a multiprocessor, and more particularly, to techniques for coordinating access to a transactional memory space.
2. Description of the Related Art
In concurrent software designs and implementations, it is often important to ensure that one thread does not observe partial results of an operation that is concurrently being executed by another thread. Such assurances are important for practical and productive software development because, without them, it can be extremely difficult to reason about the interactions of concurrent threads.
Such assurances have often been provided by using locks to prevent other threads from accessing the data affected by an ongoing operation. Unfortunately, the use of locks gives rise to a number of well known problems, both in terms of software engineering and in terms of performance. First, the right “balance” of locking must be achieved, so that correctness can be maintained, but the use of a particular lock does not prevent access to an unnecessary amount of unrelated data (thereby causing other threads to wait when they do not have to). Furthermore, if not used carefully, locks can result in deadlock, causing software to freeze up. While well documented, these and other problems are pervasive in concurrent programming, and addressing them often results in code that is complicated and expensive.
A further limitation exhibited by software that employs locks as a coordination mechanism is that, no matter how carefully used, lock implementations typically have the problem that if a thread is delayed (e.g., preempted) while holding a lock, then other threads must wait for at least the duration of that delay before being able to acquire that lock. In general, operating systems and other runtime environments cannot avoid this problem because they cannot accurately predict how long a particular lock will be held, and they cannot revoke the lock without jeopardizing correctness.
Transactional memory is a paradigm that allows the programmer to design code as if multiple memory locations can be accessed and/or modified in a single atomic step. As typically defined, a transactional memory interface allows a programmer to designate certain sequences of operations as “transactions,” which are guaranteed by the transactional memory implementation to either take effect atomically and in their entirety (in which case we say they succeed), or have no externally visible effect (in which case we say that they fail). Thus, in many cases, it is possible to complete a multi-target operation with no possibility of another thread observing partial results, even without holding any locks. The transactional paradigm can significantly simplify the design of concurrent programs.
In general, transactional memory can be implemented in hardware, with the hardware directly ensuring that a transaction is atomic, or in software that provides the “illusion” that the transaction is atomic, even though in fact it is executed in smaller atomic steps by the underlying hardware. See e.g., M. Herlihy and J. Moss, Transactional Memory Architectural Support for Lock-Free Data Structures, In Proceedings of the 20th International Symposium in Computer Architecture, pp. 289-300 (1993); N. Shavit and D. Touitou, Software Transactional Memory, Distributed Computing, Special Issue (10):99-116 (1997).
Transactional memory is widely recognized as a promising paradigm for allowing a programmer to make updates to multiple locations in a manner that is apparently atomic, while addressing many of the problems associated with the use of locks. However, certain classes of algorithms and concurrent shared objects may not be well suited to transaction memory, at least as conventionally defined. For example, transactional operations on dynamically-sized data structures (e.g., lists, trees, etc.) may not be well-suited given the substantial working set exposure accumulated in traversal of large structures. Similarly, transactional operations that perform significant computations but which can fail on a condition (e.g., buffer full) whose eventual removal or satisfaction does not necessarily undermine the validity of the prior computations, may not be well-suited to transaction memory, as conventionally defined. Accordingly, modifications to the transactional interface and corresponding exploitations for concurrent software and shared objects are desired.